算法题解 食物链

source
算法基础课界面

solution code and explain:

#include <iostream>
using namespace std;

const int N = 50010;

// f 采用正常的并查集操作，但是含意并不是两个动物是同一个物种，而是表示两个动物全都初始化(被贴上属于什么物种的标签)过了
// d 则是表示与root的距离，在此题中，如果一个 d 比另一个 d 大一，那么就表示上一个 d 可以吃掉下一个 d
int f[N], d[N];

// 经过 find 操作, f 会变成扁平化。
// 可以把 d 想象成树形，但是其实他相当于 hashmap
int find(int x) {
	if (x != f[x]) {
		int tmp = find(f[x]); // find 必须在更改 d[x] 前，考虑到递归
		d[x] += d[f[x]]; // 下次改变 d[x] 的时候如果没做其他举动就会变成 d[x] += 0 ，所以有效
		f[x] = tmp;
	}
	return f[x];
}

int main() {
	ios::sync_with_stdio(false); cin.tie(nullptr);

	int n, k;
	cin >> n >> k;

	for (int i = 1; i <= n; i ++) f[i] = i;

	int wn = 0;
	while (k --) {
		int op, x, y;
		cin >> op >> x >> y;
		
		if (x > n || y > n) {
			wn ++;
			continue;
		}

		int rx = find(x);
		int ry = find(y);
		if (op == 1) {
			if (rx == ry) { // both initialized
				if ((d[x] - d[y]) % 3) wn ++;
			} else {
				f[rx] = ry;
				d[rx] = d[y] - d[x]; // 画个图比较好理解，就是 d[x] + d[rx] = d[y]
                // 至于对于 x 以及 rx 的其余子节点的更新，在之后的 find 中会更新
			}
		} else if (op == 2) {
			if (rx == ry) { // both initialized
				if ((d[x] - d[y] - 1) % 3) wn ++;
			} else {
				f[rx] = ry;
				d[rx] = d[y] - d[x] + 1;
			}
			
		} else cout << "IMPOSSIBLE";
	}

	cout << wn << endl;
	return 0;
}